package leetcode.code0403;

/**
 * 记忆化搜索 <br>
 * 在所有 Java 提交中击败了 91.09% 的用户
 *
 * @author CaoYu
 * @date 2021年10月5日
 * @description
 */
public class Solution extends Solution403 {

	@Override
	public boolean canCross(int[] stones) {
		if (stones[1] != 1) // 第一个点都跳不上去
			return false;
		if (stones.length == 2) // 跳上去了 ,就两个长度
			return true;
		int len = stones.length;
		Boolean[][] dp = new Boolean[len][len];
		return this.canCross(stones, 1, 1, dp);// 经过k步 抵达当前位置 能否到达最后
	}

	private boolean canCross(int[] stones, int k, int first, Boolean[][] dp) {
		int last = stones.length - 1;
		if (first == last) {
			return true;
		}
		if (dp[k][first] != null)
			return dp[k][first];
		for (int i = k - 1; i <= k + 1; i++) {
			int to = stones[first] + i;// 从当前位置, 经过k-1, k , k+1的尝试能去哪
			for (int j = first + 1; j <= last; j++) {
				if (stones[j] > to) {
					break;
				}
				if (stones[j] == to) {// 能去的位置恰巧存在
					if (this.canCross(stones, i, j, dp)) { // 后续还能走到头
						dp[k][first] = true;
						return true;// 这条路对了
					}
				}
			}
		}
		dp[k][first] = false;
		return false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
		so.debug3();
//		so.debug4();
//		so.debug5();
	}

}
